package com.gaogzhen.algorithm.leetCode;

import java.util.Arrays;

/**
 * 88. 合并两个有序数组
 */
public class Merge2OrderedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 5, 20, 333, 0, 0, 0, 0, 0};
        int[] nums2 = {3, 6, 32, 222, 434};
        merge5(nums1, 4, nums2, nums2.length);
        System.out.println(Arrays.toString(nums1));
    }

    public static void merge1(int[] nums1, int m, int[] nums2, int n) {

        int len = m + n;
        int[] nums = new int[len];
        int x = 0, n1 = 0, n2 = 0;
        while (n1 < m && n2 < n) {
            if (nums1[n1] <= nums2[n2])
                nums[x++] = nums1[n1++];
            else
                nums[x++] = nums2[n2++];
        }

        while (n1 < m)
            nums[x++] = nums1[n1++];
        while (n2 < n)
            nums[x++] = nums2[n2++];

        for (int i = 0; i < len; i++) {
            nums1[i] = nums[i];
        }
    }

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
        System.out.println(Arrays.toString(nums1));
    }

    public static void merge3(int[] nums1, int m, int[] nums2, int n) {
//        int[] nums1 = {1, 5, 20, 333, 0 , 0, 0, 0, 0};
//        int[] nums2 = {3, 6, 32, 222, 434};
        int start1 = 0, start2 = 0, x = 0, end1 = m - 1;
        while (start1 <= end1 && start2 < n) {
            if (nums1[start1] > nums2[start2]) {
                for (int i = end1; i >= start1; i--) {
                    nums1[i + 1] = nums1[i];
                }
                nums1[x] = nums2[start2++];
                end1++;
            }
            x++;
            start1++;
        }
        while (start2 < n) {
            nums1[x++] = nums2[start2++];
        }
    }

    public static void merge4(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n;
        int n1 = len - 1, n2 = m - 1, x = 0;
        while (n2 >= 0)
            nums1[n1--] = nums1[n2--];
        n2++;
        n1++;
        while (n1 < len && n2 < n)
           nums1[x++] = nums1[n1] <= nums2[n2] ? nums1[n1++]: nums2[n2++];
        while (n1 < len)
            nums1[x++] = nums1[n1++];
        while (n2 < n)
            nums1[x++] = nums2[n2++];
    }

    public static void merge5(int[] nums1, int m, int[] nums2, int n) {
        int n1 = m - 1, n2 = n - 1, x = m + n -1;
        while (n1 >= 0 && n2 >= 0) {
            if (nums1[n1] > nums2[n2]) {
                nums1[x] = nums1[n1--];
            } else {
                nums1[x] = nums2[n2--];
            }
            x--;
        }
        if (n1 >= 0) {
            while (n1 >= 0) {
                nums1[x--] = nums1[n1--];
            }
        }
        if (n2 >= 0) {
            while (n2 >= 0) {
                nums1[x--] = nums2[n2--];
            }
        }
    }
}
